package hzk.codex2016.list;

public class LinkedList_reorders {

	/**
	 * https://leetcode.com/problems/palindrome-linked-list/
	 * 
	 * @param head
	 * @return
	 */

	public boolean isPalindrome(ListNode head) {
		if (head==null || head.next==null) return true;
		int len=1;
		ListNode p=head;
		while ((p=p.next)!=null) len++;
		int k=(len+1)/2;
		ListNode rhead=head;
		while (k-->0) rhead=rhead.next;
		
		//reverse the right part
		ListNode tmp,q,pre=rhead;
		p=pre.next;
		pre.next=null;
		while (p!=null){
			tmp=p.next;
			p.next=pre;
			pre=p;
			p=tmp;
		}
		p=head;
		q=pre;	//now pre is tail
		
		while (q!=null){
			if (p.val!=q.val) return false;
			p=p.next;
			q=q.next;
			
		}
		
		return true;
		
		
	}
	
	/**
	 * https://leetcode.com/problems/odd-even-linked-list/
	 */
	public ListNode oddEvenList(ListNode head) {
		if (head==null || head.next==null) return head;
        ListNode odd=head,even=head.next,p=even.next,q,tmp;
        ListNode odd1=odd,even1=even;//tails
        while (p!=null){
        	odd1=odd1.next=p;        	
        	q=p.next;
        	p.next=null;
        	if (q==null) break;
        	p=q.next;
        	q.next=null;
        	even1=even1.next=q;
        }
        even1.next=null;
        odd1.next=even;
        return odd;
    }
	/**
	 * https://leetcode.com/problems/intersection-of-two-linked-lists/
	 */
	 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	 	if (headA==null || headB==null) return null;
        int lenA=1;
        ListNode p=headA;
        while ((p=p.next)!=null) lenA++;
        int lenB=1;
        p=headB;
        while ((p=p.next)!=null) lenB++;
         
        while (lenA>lenB) {headA=headA.next;lenA--;}
        while (lenA<lenB) {headB=headB.next;lenB--;}
        while (headA!=headB && headA!=null && headB!=null){
        	headA=headA.next;
        	headB=headB.next;
        }
        return headA;
        
	 }
	 
	public static void main(String[] args) {
		LinkedList_reorders p = new LinkedList_reorders();
		System.out.println(p.isPalindrome(Lists.sll(1,2,3,4)));
		System.out.println(p.isPalindrome(Lists.sll(1,2,2,1)));
		System.out.println(p.isPalindrome(Lists.sll(1,2,3,2,1)));
		System.out.println(p.isPalindrome(Lists.sll(1,2,3,2,2)));
		System.out.println(p.isPalindrome(Lists.sll(2,2,2,2)));
		System.out.println(p.isPalindrome(Lists.sll(1,2)));
		
		System.out.println(p.oddEvenList(Lists.sll(1)));
		System.out.println(p.oddEvenList(Lists.sll(1,2)));
		System.out.println(p.oddEvenList(Lists.sll(1,2,3)));
		System.out.println(p.oddEvenList(Lists.sll(1,2,3,4)));
		System.out.println(p.oddEvenList(Lists.sll(1,2,3,4,5,6,7,8,9)));
		
		ListNode a=Lists.sll(1,2,3,4);
		ListNode b=Lists.sll(5,6,7,8,9);
		b.tail().next=a.next(0);
		System.out.println(p.getIntersectionNode(a,b));
	}
}
